The present invention relates to a technique on Viterbi decoding for decoding a trellis-coded modulated signal.
As a conventional configuration for decoding a trellis-coded modulated signal, a Viterbi decoder as shown in FIG. 13 has been proposed (Japanese Laid-Open Patent Publication No. 5-335972; corresponding U.S. Pat. No. 5,509,021).
FIG. 11 shows a trellis encoder that generates the trellis-coded modulated signal to be decoded by the above conventional decoder. FIG. 12 is a trellis diagram for the trellis encoder in FIG. 11. The trellis encoder in FIG. 11 has an encoding rate of ¾ with one noncoding bit and a constraint length of 4. Therefore, this trellis encoder has 2(4-1)=8 states that are represented by values of registers D2, D1, and D0 of the encoder, that is, {000}, {001}, {010}, {011}, {100}, {101}, {110}, and {111}. In addition, the values of outputs {y2, y1, y0} of the encoder constitute a subset, and the value of this bit string as binary notation is herein defined as the number of this subset. For example, if {y2, y1, y0}={1, 0, 1}, the subset number is “5”, and this subset is referred to as “subset s5”. Such subsets s0 through s7 are called subsets A through H in the aforementioned prior art.
The operation of the Viterbi decoder in FIG. 13 is as follows.
A branch metric generator 601 determines Euclidean distances between a reception signal point and respective transmission symbol points, and outputs the results as branch metrics “BMs” (“s” denotes any of the subset numbers 0 to 7). One subset includes two transmission symbol candidates. A branch metric corresponding to the transmission symbol string of which the noncoding bit is “0” is denoted by BMs0, while a branch metric corresponding to the transmission symbol string of which the noncoding bit is “1” is denoted by BMs1.
A subset maximum likelihood estimator 602 selects one of the two transmission symbol candidates of each subset that has a smaller Euclidean distance, and outputs the selected one as the branch metric BMs for the subset concerned.
A noncoding bit detector 603 extracts the noncoding bit in each selected transmission symbol candidate based on the selection information output from the subset maximum likelihood estimator 602, and outputs the extracted noncoding bit. The noncoding bits are then delayed by j-level shift registers 604 by j levels that correspond to the number of delay levels in a path memory circuit 607.
An add-compare-select (ACS) circuit 605 adds the branch metrics output from the subset maximum likelihood estimator 602 to path metrics of survivor paths in each state at time t-1, that is, in a state before transition to a state at time t in the trellis diagram shown in FIG. 12. The ACS circuit 605 then selects one of the added values that has the highest likelihood as a path metric PM0 to PM7 of the survivor path. Simultaneously, the selection information is output as a select signal PS0 to PS7.
FIG. 14 is a block diagram of a basic unit of the ACS circuit. For simplifying the description, FIG. 14 illustrates only a basic unit corresponding to state i. In the case of the above conventional decoder, since the number of states is 8, a total of eight basic units with the configuration shown in FIG. 14 are arranged in parallel in the ACS circuit 605.
Adders 700a to 700d receive path metrics PMa to PMd and branch metrics BMa to BMd in accordance with the trellis diagram shown in FIG. 12. The respective added results a to d are input into a comparator 701. The comparator 701 compares the added results a to d, selects one having the highest likelihood, and outputs a select signal PSi representing the selected result. Specifically, if the added result a is selected, “0” is output. Likewise, if the added results b, c, and d are selected, “1”, “2”, and “3” are output, respectively. A selector 702 receives the added results a to d and the select signal PSi, and outputs to a register 703 one of the added results that corresponds to the select signal PSi as a new path metric PMi for state i.
The order of {(PMa,BMa), (PMb,BMb), (PMc,BMc), (PMd,BMd)} input into the basic unit is set as follows for the respective states in the above conventional decoder.
<State 0>
    {(PM0,BM0), (PM2,BM4), (PM4,BM2), (PM6,BM6)}<State 1>    {(PM0,BM4), (PM2,BM0), (PM4,BM6), (PM6,BM2)}<State 2>    {(PM0,BM2), (PM2,BM6), (PM4,BM0), (PM6,BM4)}<State 3>    {(PM0,BM6), (PM2,BM2), (PM4,BM4), (PM6,BM0)}<State 4>    {(PM1,BM1), (PM3,BM5), (PM5,BM3), (PM7,BM7)}<State 5>    {(PM1,BM5), (PM3,BM1), (PM5,BM7), (PM7,BM3)}<State 6>    {(PM1,BM3), (PM3,BM7), (PM5,BM1), (PM7,BM5)}<State 7>    {(PM1,BM7), (PM3,BM3), (PM5,BM5), (PM7,BM1)}
The path select signals PS0 to PS7 output from the ACS circuit 605 are input into the path memory 607. FIG. 15 illustrates the path memory 607, which is basically configured to concretize the transitions to respective nodes in the trellis diagram. Registers disposed at positions corresponding to the nodes store values selected among those output from the immediately preceding registers in accordance with the respective path select signals PS0 to PS7.
At the first level, the subset number itself is selected by the path select signal PSi. Accordingly, the subset numbers at each branch in the trellis diagram in FIG. 12 are input into a selector 800. For example, in state 0, when the path select signal PS0 is “0”, (PM0,BM0) has been selected. Therefore, the selector 800 outputs the subset number “0”, which is stored in a register 801. Likewise, when the path select signal PS0 is “1”, “2”, and “3”, the selector 800 outputs the subset number “4”, “2”, and “6”, respectively. In states 1 to 7, also, the selector 800 outputs a subset number x corresponding to each of the path select signals PS1 to PS7. The output results are stored in the respective registers 801.
At the second level, a value stored in a register corresponding to the node number at the first level is selected. For example, in state 0, when the path select signal PS0 is “0”, (PM0,BM0) has been selected. Therefore, a selector 802 outputs the content of the register corresponding to state 0 at the first level, which is then stored in a register 803. Likewise, when the path select signal PS0 is “1”, “2”, and “3”, the selector 802 outputs the content of register 2, 4, and 6, respectively. In states 1 to 7, also, the selector 802 outputs the content of register x at the first level corresponding to the state number x represented by the value of each of the path select signals PS1 to PS7. The output results are stored in the respective registers 803.
The above configuration at the second level is repeated for the third and subsequent levels until the j-th level. In this way, values are shifted from the first level through the j-th level for j clocks. Thus, a value stored in register n at the j-th level is equal to the subset number in the state through which the survivor path in state n has passed j time points earlier. The outputs from the registers at the j-th level are input into a selector 608.
A most likely path decision circuit 606 receives the outputs PM0 to PM7 from the registers of the respective basic units of the ACS circuit 605, detects the state having the highest likelihood among the inputs, and outputs the number of the detected state. Selector 608 receives the output of the most likely path decision circuit 606 and selects the corresponding register output value. The register output value is equal to the subset number that will be obtained by going back along the most likely path by j levels. In the case of the encoder shown in FIG. 11, the two higher-order bits of the subset number are equal to the bits of input information. Accordingly, the two higher-order bits of the subset number output from the selector 608 represent decoded coding bits (x2,x1). Further, based on the decoded subset number output from the selector 608, a selector 609 selects a noncoding bit x3 delayed by j levels for the subset number. The noncoding bit x3 in combination with the coding bits (x2,x1) are output as the decoding results of the Viterbi decoder.
The above conventional configuration has the following problems.
First, used conventionally as the path memory is the configuration as shown in FIG. 15 composed of combinations of selectors and registers, just concretizing the trellis diagram. Accordingly, if the truncation length (j levels in this case) increases or the number of states in the encoder increases, the circuit size of the path memory markedly increases. This results in significant increase in the circuit area of the entire device and power consumption.
Secondly, in the path memory as shown in FIG. 15, connections to the respective selectors are unique to a specific encoder. It is therefore difficult to configure a general-purpose decoder usable for different encoders.
Thirdly, the path memory conventionally stores subset numbers themselves. With this configuration, when the encoding rate of a trellis encoder is reduced by increasing the number of bits of a code from 3 to 4 or even 5, for example, the number of bits of each subset number increases thereby increasing the number of bits stored in the path memory. This also results in increase in the circuit area of the entire device.